3D Coding TAT - "Noah" - Flood Fill Rendering
When I first thought about 3d engines and ways to render levels I did get too close to the problem and was unable to see any further than my polygon nose. Sometimes it's beneficial to adapt techniques from unrelated problems to the current one even if the connection is not obvious. I reckon most programmers when learning 3d stuff try to modify exsisting 2d methods to work in the 3rd dimension. A good example of this it tiled (or grid-based) levels. The entire game world area is divided into equally spaced cells and each cell can represent a wall, a hill a door or whatever. Games like Wolfenstein, System-Shock, Raise of the Triads and even both Tomb Raider games appear to use this method in some form. It has some advantages:
1. Levels are easier to design.
2. Components can be used again and again simply by using the indentical cell code for a door, wall etc.
3. Rendering can be sped up as walls meet at 90° and spacing is constant.
But also has some disadvantages:
1. Levels look very much alike.
2. Rooms all look like breeze-blocks.
Games which are platform orientated seem to like this map/cell approach because designers can just count the cells between two platforms knowing that a player can or can not make the leap to the other side.
One of the reasons why the map/cell method is used in 3d games is because it automattically fixes a local relationship between neighbouring cells in terms of distance and direction. A speed advantage is gained because we simply choose a starting cell and render from that point. We scan across the map from our starting point and render the walls/doors etc. as we go. As the adjoining level structures are described in the adjoining map cell almost all the searching and depth sorting can be minimize a great deal. You could think of this cell (or 2d "array") rendering as a form of flood-fill algorithm where we trace along the wall edges and stop at closed doors or other obstacles. Of course you would also need to consider cells/areas behind your view point as also being a kind of boundary where rendering also stops. I have not seen any 3d engines (not even part of one) but I hazard a guess that a form of filling is used. Wolfenstein and Doom to my knowledge used "Ray Casting" to render the view point, so you could describe that as a form of render fill, again beginning at the starting cell and working outwards from the view point.
But a problem with the flood-fill idea of drawing a 3d scene is that it is possible that overdraw can occur when we follow a wall which goes around the back of a closer wall. This is because a standard flood-fill algorithm will simply keep flooding in the same direction until it encounters a wall/door boundary. In the worst possible case it may have filled entirely to the far side of the level before a dead end is met. You could use a limiting check for distance or number of cells filled and then halt the rendering at that point, but still the problem of overdraw may occur because we could be tracing distant walls before checking whether a closer one obscures it.
For example if we start at the left edge of the screen and trace along a map following wall/door boundaries then it is possible that we end up behind a wall on the right of the screen or we may even drift left completely beyond our view. What we need to do is only continue to fill if a part of the connected cell can actually be seen from our viewpoint.
Another approach could be to scan outwards from our starting cell in a circle (or semicircle as only 180° can be seen). This does have the advantage that ALL the walls/obstructions at a certain distance will be found at the same time (at the same distance from us). This should help avoid the dead-end fill problem and hopefully sorting will be minimized too. I guess this is how "Ray-Casting" was developed. Like an expanded radar ping from the centre, anything which it hits halts the current ray in that direction. A simple approach could be to start 320 rays from our view point (1 for each horizontal X coordinate on our screen) and only continue to trace along the map if no obstruction has been met, otherwise we simply draw what we encountered taking into account the distance we have traced along the map and delete the ray.